/**
 * 面试题51：数组中的逆序对
 */
public class Offer_51 {
    /**
     * 归并排序思想
     * <p>
     * 时间复杂度：O(nlogn)
     * <p>
     * 空间复杂度：O(n)
     */
    public int reversePairs(int[] nums) {
        // 辅助数组
        int[] temp = new int[nums.length];
        return mergeSort(nums, 0, nums.length - 1, temp);
    }

    /**
     * 归并排序
     * 
     * @param nums  待排序数组
     * @param left  待排序区间起点索引
     * @param right 待排序区间终点索引（包含）
     * @param temp  辅助数组
     * @return 数组中逆序对的数量
     */
    private int mergeSort(int[] nums, int left, int right, int[] temp) {
        // 递归出口
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        // 递归
        int ans = mergeSort(nums, left, mid, temp) + mergeSort(nums, mid + 1, right, temp);

        // 合并
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            temp[k] = nums[k];
        }
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                // 如果左半部分已访问完
                nums[k] = temp[j++];
            } else if (j > right) {
                // 如果右半部分已访问完
                nums[k] = temp[i++];
            } else if (temp[i] <= temp[j]) {
                // 如果当前左半部分元素较小
                nums[k] = temp[i++];
            } else {
                // 如果当前右半部分元素较小
                nums[k] = temp[j++];
                // 计算逆序对数量
                ans += mid - i + 1;
            }
        }
        return ans;
    }
}
